AVL自平衡树——数据结构系列教程(c++版)

#ifndef LINKEDAVLTREE_H_INCLUDED
#define LINKEDAVLTREE_H_INCLUDED

#include "Entitys.h"

//========================================================================================================================================================================
//
//                                                                 AVL节点结构体(AVLNode)
//
//========================================================================================================================================================================
template <typename T>
struct AVLNode {
    T data;               // 模板化数据域，支持任意类型
    AVLNode* left;        // 左节点指针指针
    AVLNode* right;       // 右节点指针
    int height;           // 节点高度（叶子节点高度为1）
};

//========================================================================================================================================================================
//
//                                                                 AVL自平衡树结构体(LinkedAVLTree)
//
//========================================================================================================================================================================
template <typename T>
struct LinkedAVLTree{
    //------------------------------------------------------------------------------------------------------
    //                                          私有成员
    // 注：私有成员只能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)不能访问调用）
    //------------------------------------------------------------------------------------------------------
    private:

        //---------------声明私有成员变量---------------

        AVLNode<T>* root = nullptr;   // 模板类型根节点指针
        int level = 0;                // 用于跟踪搜索树的层次
        int depth = 0;                // 用于跟踪搜索树的深度
        int qty = 0;                  // 用于跟踪搜索树的节点数量

        //---------------声明私有成员函数---------------

        int getHeight(AVLNode<T>* node);// 获取节点高度（空节点高度为0）
        void updateHeight(AVLNode<T>* node);// 更新节点高度（基于左右子树高度）
        int getBalanceFactor(AVLNode<T>* node);// 计算平衡因子（左子树高度 - 右子树高度）
        AVLNode<T>* createAVLNode(const T& val); // 创建新的AVL节点（模板类型） 用const&避免拷贝开销
        AVLNode<T>* findMin(AVLNode<T>* node);// 辅助函数：找右子树的最小节点（删除节点时用）
        AVLNode<T>* rightRotate(AVLNode<T>* y);// 右旋（处理左左失衡）
        AVLNode<T>* leftRotate(AVLNode<T>* x);// 左旋（处理右右失衡）
        AVLNode<T>* insertNode(AVLNode<T>* node, const T& val);// 插入节点（递归版本）
        AVLNode<T>* insertNodeIter(AVLNode<T>* node, const T& val);// 插入节点（迭代版本）
        AVLNode<T>* deleteNode(AVLNode<T>* node, const T& val);// 删除节点（模板类型）
        T searchNode(AVLNode<T>* node, const T& val);// 查找节点（模板类型）
        void preOrder(AVLNode<T>* node);// 前序遍历（根 → 左 → 右）
        void inOrder(AVLNode<T>* node);// 中序遍历（左 → 根 → 右）→ 升序输出
        void postOrder(AVLNode<T>* node);// 后序遍历（左 → 右 → 根）
        void destroyAVLTree(AVLNode<T>* node);// 销毁整棵树（防止内存泄漏）

    //------------------------------------------------------------------------------------------------------
    //                                          公共成员
    // 注：公共成员能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)也能访问调用）
    //------------------------------------------------------------------------------------------------------
    public:

        //---------------声明公共成员函数---------------

        // 构造函数：外部通过该结构体定义(实例化)变量(对象)时，自动执行该函数(主要用于初始化成员变量的值)
        LinkedAVLTree() {
            root = nullptr; // 初始化为空树
            level = depth = qty = 0;
        }
        int isEmpty();// 判断搜索树是否为空
        int isFull();// 判断搜索树是否已满（链表实现永远不满）
        int getHeight();// 获取树的高度（根节点高度）
        int getBalanceFactor();// 计算根节点的平衡因子
        void insertNode(const T& val);// 插入节点（对外接口，模板类型）
        void deleteNode(const T& val);// 删除节点（对外接口，模板类型）
        T searchNode(const T& val);// 查找节点（对外接口，模板类型）
        void preOrder();// 前序遍历（对外接口）
        void inOrder();// 中序遍历（对外接口）
        void postOrder();// 后序遍历（对外接口）
        void destroyTree();// 销毁整棵树（防止内存泄漏）

        // 析构函数：自动销毁树，避免内存泄漏
        ~LinkedAVLTree() {
            destroyTree();
        }
};

#endif // LINKEDAVLTREE_H_INCLUDED

5.3 LinkedAVLTree.cpp 程序代码

#include <iostream>
#include <cstdlib> 
#include "LinkedAVLTree.h"

//---------------实现私有成员函数---------------

// 获取节点高度（空节点高度为0）
template <typename T>
int LinkedAVLTree<T>::getHeight(AVLNode<T>* node)
{
    return node == nullptr ? 0 : node->height;
}

// 更新节点高度（基于左右子树高度）
template <typename T>
void LinkedAVLTree<T>::updateHeight(AVLNode<T>* node)
{
    if (node == nullptr) return;
    int leftH = getHeight(node->left);
    int rightH = getHeight(node->right);
    node->height = (leftH > rightH ? leftH : rightH) + 1;
}

// 计算平衡因子（左子树高度 - 右子树高度）
template <typename T>
int LinkedAVLTree<T>::getBalanceFactor(AVLNode<T>* node)
{
    return node == nullptr ? 0 : getHeight(node->left) - getHeight(node->right);
}

// 创建新的AVL节点（模板类型）
template <typename T>
AVLNode<T>* LinkedAVLTree<T>::createAVLNode(const T& val)
{
    AVLNode<T>* node = new AVLNode<T>(); // 动态分配模板类型节点
    if (node == nullptr) {
        perror("new failed");
        exit(EXIT_FAILURE);
    }
    node->data = val;
    node->left = node->right = nullptr;
    node->height = 1; // 叶子节点高度初始化为1
    qty++; // 节点数+1
    return node;
}

// 辅助函数：找右子树的最小节点（删除节点时用）
template <typename T>
AVLNode<T>* LinkedAVLTree<T>::findMin(AVLNode<T>* node)
{
    while (node->left != nullptr) node = node->left;
    return node;
}

// ===================== 旋转操作（核心） =====================
// 右旋（处理左左失衡）
template <typename T>
AVLNode<T>* LinkedAVLTree<T>::rightRotate(AVLNode<T>* y)
{
    AVLNode<T>* x = y->left;
    AVLNode<T>* B = x->right;

    // 执行旋转
    x->right = y;
    y->left = B;

    // 更新高度（先更新y，再更新x，因为x是y的父节点）
    updateHeight(y);
    updateHeight(x);

    return x; // 返回新的根节点
}

// 左旋（处理右右失衡）
template <typename T>
AVLNode<T>* LinkedAVLTree<T>::leftRotate(AVLNode<T>* x)
{
    AVLNode<T>* y = x->right;   // y是x的右子
    AVLNode<T>* B = y->left;

    // 执行旋转
    y->left = x;
    x->right = B;

    // 更新高度
    updateHeight(x);
    updateHeight(y);

    return y; // 返回新的根节点
}

// 插入节点（递归版本）
template <typename T>
AVLNode<T>* LinkedAVLTree<T>::insertNode(AVLNode<T>* node, const T& val) {
    // 1. 普通BST插入逻辑（适配模板类型比较）
    if (node == nullptr) return createAVLNode(val);
    if (val < node->data) { // 模板类型需支持<运算符
        node->left = insertNode(node->left, val);
    } else if (val > node->data) { // 模板类型需支持>运算符
        node->right = insertNode(node->right, val);
    } else {
        // 重复值，AVL树不存储重复值
        return node;
    }

    // 2. 更新当前节点高度
    updateHeight(node);

    // 3. 计算平衡因子，判断是否失衡
    int balance = getBalanceFactor(node);

    // 4. 失衡处理（4种情况）
    // 情况1：左左失衡（LL）→ 右旋
    if (balance > 1 && val < node->left->data) {
        return rightRotate(node);
    }
    // 情况2：右右失衡（RR）→ 左旋
    if (balance < -1 && val > node->right->data) {
        return leftRotate(node);
    }
    // 情况3：左右失衡（LR）→ 先左旋左子树，再右旋根
    if (balance > 1 && val > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    // 情况4：右左失衡（RL）→ 先右旋右子树，再左旋根
    if (balance < -1 && val < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    // 未失衡，返回原节点
    return node;
}

// 插入节点（迭代版本）
template <typename T>
AVLNode<T>* LinkedAVLTree<T>::insertNodeIter(AVLNode<T>* node, const T& val) {
    // 处理根节点为空的特殊情况
    if (node == nullptr) {
        return createAVLNode(val);
    }

    AVLNode<T>* current = node;  // 遍历指针，从根节点开始
    AVLNode<T>* parent = nullptr; // 记录当前节点的父节点

    // 迭代查找插入位置
    while (current != nullptr) {
        parent = current; // 更新父节点为当前节点

        if (val < current->data) { // 小于当前节点，向左子树查找
            current = current->left;
        } else if (val > current->data) { // 大于当前节点，向右子树查找
            current = current->right;
        } else {
            // 找到重复值，直接返回原根节点（不插入）
            return node;
        }
    }

    // 找到插入位置，创建新节点并挂载到父节点的左/右子树
    AVLNode<T>* newNode = createAVLNode(val);
    if (val < parent->data) {
        parent->left = newNode;
    } else {
        parent->right = newNode;
    }

    // 2. 更新当前节点高度
    updateHeight(node);

    // 3. 计算平衡因子，判断是否失衡
    int balance = getBalanceFactor(node);

    // 4. 失衡处理（4种情况）
    // 情况1：左左失衡（LL）→ 右旋
    if (balance > 1 && val < node->left->data) {
        return rightRotate(node);
    }
    // 情况2：右右失衡（RR）→ 左旋
    if (balance < -1 && val > node->right->data) {
        return leftRotate(node);
    }
    // 情况3：左右失衡（LR）→ 先左旋左子树，再右旋根
    if (balance > 1 && val > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    // 情况4：右左失衡（RL）→ 先右旋右子树，再左旋根
    if (balance < -1 && val < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    // 未失衡，返回原节点
    return node;
}

// 删除节点（模板类型）
template <typename T>
AVLNode<T>* LinkedAVLTree<T>::deleteNode(AVLNode<T>* node, const T& val) {
    // 1. 普通BST删除逻辑
    if (node == nullptr) return nullptr;

    if (val < node->data) {
        node->left = deleteNode(node->left, val);
    } else if (val > node->data) {
        node->right = deleteNode(node->right, val);
    } else {
        // 找到要删除的节点，处理3种情况
        AVLNode<T>* temp = nullptr;

        // 情况1：叶子节点（左右子树都为空）
        if (node->left == nullptr && node->right == nullptr) {
            temp = node;
            node = nullptr; // 置空当前节点，让父节点指向NULL
            delete temp;    // 释放内存
            qty--; // 节点数-1
        }
        // 情况2：只有一个子树（左空或右空）
        else if (node->left == nullptr || node->right == nullptr) {
            temp = node->left ? node->left : node->right; // 取非空子树
            delete node; // 释放当前节点
            node = temp; // 让当前节点指向子树（替代原节点）
            qty--; // 节点数-1
        }
        // 情况3：有两个子树 → 找右子树最小值节点（后继）
        else {
            temp = findMin(node->right);
            node->data = temp->data; // 替换值
            node->right = deleteNode(node->right, temp->data); // 删除后继节点
        }
    }

    // 如果树只剩一个节点，直接返回
    if (node == nullptr) return nullptr;

    // 2. 更新当前节点高度
    updateHeight(node);

    // 3. 计算平衡因子，判断是否失衡
    int balance = getBalanceFactor(node);

    // 4. 失衡处理（4种情况）
    // 情况1：左左失衡（LL）
    if (balance > 1 && getBalanceFactor(node->left) >= 0) {
        return rightRotate(node);
    }
    // 情况2：左右失衡（LR）
    if (balance > 1 && getBalanceFactor(node->left) < 0) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    // 情况3：右右失衡（RR）
    if (balance < -1 && getBalanceFactor(node->right) <= 0) {
        return leftRotate(node);
    }
    // 情况4：右左失衡（RL）
    if (balance < -1 && getBalanceFactor(node->right) > 0) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    // 未失衡，返回原节点
    return node;
}

// 查找节点（模板类型）
template <typename T>
T LinkedAVLTree<T>::searchNode(AVLNode<T>* node, const T& val) {
    if (node == nullptr) { // 未找到
        return T();
    }
    if (val == node->data) { // 模板类型需支持==运算符
        return node->data;
    } else if (val < node->data) { // 往左子树找
        return searchNode(node->left, val);
    } else { // 往右子树找
        return searchNode(node->right, val);
    }
}

// 前序遍历（根 → 左 → 右）
template <typename T>
void LinkedAVLTree<T>::preOrder(AVLNode<T>* node) {
    if (node == nullptr) return;
    // 模板类型需支持<<运算符（或自定义打印逻辑）
    std::cout << node->data << " (H: " << node->height << ", BF: " << getBalanceFactor(node) << ") ";
    preOrder(node->left);
    preOrder(node->right);
}

// 中序遍历（左 → 根 → 右）→ 升序输出
template <typename T>
void LinkedAVLTree<T>::inOrder(AVLNode<T>* node) {
    if (node == nullptr) return;
    inOrder(node->left);
    std::cout << node->data << " (H: " << node->height << ", BF: " << getBalanceFactor(node) << ") ";
    inOrder(node->right);
}

// 后序遍历（左 → 右 → 根）
template <typename T>
void LinkedAVLTree<T>::postOrder(AVLNode<T>* node) {
    if (node == nullptr) return;
    postOrder(node->left);
    postOrder(node->right);
    std::cout << node->data << " (H: " << node->height << ", BF: " << getBalanceFactor(node) << ") ";
}

// 销毁整棵树（防止内存泄漏）
template <typename T>
void LinkedAVLTree<T>::destroyAVLTree(AVLNode<T>* node)
{
    if (node == nullptr) return;
    destroyAVLTree(node->left);
    destroyAVLTree(node->right);
    delete node; // 释放模板类型节点
    qty--;
}

//---------------实现公共成员函数---------------

// 判断搜索树是否为空
template <typename T>
int LinkedAVLTree<T>::isEmpty()
{
    return root == nullptr ? 1 : 0;
}

// 判断搜索树是否已满（链表实现永远不满，返回0）
template <typename T>
int LinkedAVLTree<T>::isFull() {
    return 0;
}

// 获取树的高度（根节点高度）
template <typename T>
int LinkedAVLTree<T>::getHeight()
{
    return getHeight(root);
}

// 计算根节点的平衡因子
template <typename T>
int LinkedAVLTree<T>::getBalanceFactor()
{
    return getBalanceFactor(root);
}

// 插入节点（对外接口）
template <typename T>
void LinkedAVLTree<T>::insertNode(const T& val)
{
    root = insertNode(root, val);
}

// 删除节点（对外接口）
template <typename T>
void LinkedAVLTree<T>::deleteNode(const T& val)
{
    root = deleteNode(root, val);
}

// 查找节点（对外接口）
template <typename T>
T LinkedAVLTree<T>::searchNode(const T& val)
{
    return searchNode(root, val);
}

// 前序遍历（对外接口）
template <typename T>
void LinkedAVLTree<T>::preOrder()
{
    preOrder(root);
    std::cout << std::endl; // 换行，优化输出
}

// 中序遍历（对外接口）
template <typename T>
void LinkedAVLTree<T>::inOrder()
{
    inOrder(root);
    std::cout << std::endl; // 换行，优化输出
}

// 后序遍历（对外接口）
template <typename T>
void LinkedAVLTree<T>::postOrder()
{
    postOrder(root);
    std::cout << std::endl; // 换行，优化输出
}

// 销毁整棵树（防止内存泄漏）
template <typename T>
void LinkedAVLTree<T>::destroyTree()
{
    destroyAVLTree(root);
    root = nullptr;
    printf("\n===== 树内存已全部释放 =====\n");
}

// 显式实例化常用类型（避免链接错误，可选）
template class LinkedRBTree<int>;
template class LinkedRBTree<char>;
template class LinkedRBTree<float>;
template class LinkedBSTree<std::string>;
template class LinkedAVLTree<Student>; // 新增：显式实例化Student类型
template class LinkedAVLTree<StudentIndex>; // 新增：显式实例化StudentIndex类型

5.4 main.cpp 测试代码

#include "LinkedAVLTree.h"
#include <iostream>
#include <string>

int main() {
    // ==================== 测试1：int类型AVL自平衡树 ====================
    LinkedAVLTree<int> intTree;
    int intKeys[] = {10, 20, 30, 15, 25, 5, 8};
    int n = sizeof(intKeys)/sizeof(intKeys[0]);

    // 插入int节点
    std::cout << "=== Insert int keys: ";
    for (int i = 0; i < n; i++) {
        std::cout << intKeys[i] << " ";
        intTree.insertNode(intKeys[i]);
    }
    std::cout << "===" << std::endl;

    intTree.preOrder();

    // 查找测试
    int target = 31;
    if (intTree.searchNode(target)) {
        std::cout << "\nFound " << target << " in int tree!" << std::endl;
    }

    // 删除测试
    int deleteKey = 5;
    std::cout << "\n=== Delete key: " << deleteKey << " ===" << std::endl;
    intTree.deleteNode(deleteKey);
    // 前序遍历
    intTree.preOrder();

    // 销毁树（析构函数自动调用，此处显式调用演示）
    intTree.destroyTree();
    
    return 0;
}

六、注意事项

七、总结

AVL树是最经典的自平衡二叉搜索树，核心是通过平衡因子检测失衡，并通过旋转恢复平衡，保证树的高度为log₂n级别，从而优化查找/插入/删除效率。

提供的代码实现了模板化的AVL树，支持任意类型数据，封装了核心操作的私有实现和简洁的公共接口，可直接复用。使用时需注意模板类型的运算符重载，以及内存泄漏问题（代码已通过析构函数处理）。

通过本教程，你可以掌握AVL树的原理、核心操作的实现逻辑，以及实际使用方法，适用于需要高效查找/插入/删除的场景（如数据库索引、缓存系统等）。